package com.fmm.hard;

public class PalindromicManacher {

    /**
     * @param s 字符串 s
     * @return 最长回文子串
     */
    public static String longestSubPalindrome(String s) {
        // 原始字符串转换成数组，每个字符中间插入特殊符号，包括两个端点，所以长度是 * 2 + 1
        char[] sCharArray = init(s);
        // 辅助数组，每个元素记录以当前 index 为中心的最长回文的半径长度
        int[] supportArray = new int[sCharArray.length];
        // 子回文字的最大右边界下标
        int maxRBoundary = 0;
        // 子回文字的最大右边界对应的中心位置下标
        int maxRBoundaryCenter = 0;
        for (int i = 0; i < sCharArray.length; i++) {
            // 记录以当前 i 为中心的回文半径长度
            int radius = 0;
            while (i - radius > 0 && i + radius < sCharArray.length - 1
                    && (sCharArray[i - radius - 1] == sCharArray[i + radius + 1])) {
                // 马拉车算法
                if (maxRBoundary <= (i + radius)) {
                    radius++;
                } else {
                    radius = Math.min(maxRBoundary - i, supportArray[2 * maxRBoundaryCenter - i]);
                }
            }
            // 更新辅助数组的半径
            supportArray[i] = radius;
            // 更新子回文所达到的最大范围
            if (radius > 0 && i + radius > maxRBoundary) {
                maxRBoundary = i + radius;
                maxRBoundaryCenter = i;
            }
        }

        // 辅助构建完成，找到辅助数组里最大的半径范围
        int maxRadius = 0;
        int maxRadiusIndex = 0;
        for (int i = 0; i < supportArray.length; i++) {
            if (maxRadius < supportArray[i]) {
                maxRadius = supportArray[i];
                maxRadiusIndex = i;
            }
        }

        // 去掉没用的 # 号
        StringBuilder rBuilder = new StringBuilder();
        for (int i = maxRadiusIndex - maxRadius; i <= maxRadiusIndex + maxRadius; i++) {
            if (sCharArray[i] == '#') {
            } else {
                rBuilder.append(sCharArray[i]);
            }
        }
        return rBuilder.toString();
    }

    // 构建原始 s 字符串的初始字符数组，形如："^a#b#c#d#e#f#g$"
    private static char[] init(String s) {
        char[] result = new char[s.length() * 2 + 1];
        for (int i = 0; i < result.length; i++) {
            if (i == 0) {
                result[i] = '^';
            } else if (i == result.length - 1) {
                result[i] = '$';
            } else if (i % 2 == 0) {
                result[i] = '#';
            } else {
                result[i] = s.charAt((i - 1) / 2);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(PalindromicManacher.longestSubPalindrome("bbbab"));
        System.out.println(PalindromicManacher.longestSubPalindrome("babad"));
        System.out.println(PalindromicManacher.longestSubPalindrome("caabbaaa"));
    }
}
